using System;
using System.Collections;


namespace CKM_Komiwojazer
{
	/// <summary>
	/// Sciezka opisujaca podroz komiwojazera.
	/// </summary>
	public class Sciezka
	{
        /// <summary>
        /// Tablica w ktorej de facto przechowywane sa kolejne miasta.
        /// </summary>	
        private int[] sciezka;

        /// <summary>
        /// Generator liczb pseudolosowych.
        /// </summary>
        private static Random generator = new Random();

        /// <summary>
        /// Zwraca dlugosc sciezki
        /// </summary>
        public int Dlugosc
        {
            get
            {
                return sciezka.Length;
            }
        }

        /// <summary>
        /// Konstruktor siezki komiwojazera. Domyslnie wypelnia kolejne pozycje
        /// liczbami 1, 2, .., n.
        /// </summary>
        /// <param name="n">liczba miast w siezce</param>
        public Sciezka(int n)
        {
            sciezka = new int[n];
            for (int i = 0; i < sciezka.Length; i++)
            {
                sciezka[i] = i + 1;
            }
        }

        /// <summary>
        /// Tworzy <c>String</c> opisujacy sciezke.
        /// </summary>
        /// <returns>string z opisem sciezki</returns>
        public override String ToString()
        {
            String wynik = "Sciezka (";
            foreach (int elem in sciezka)
            {
                wynik += "" + elem + " ";
            }
            wynik += ")";
            return wynik;
        }

        /// <summary>
        /// Przyrownuje dwa obiekty klasy <c>Sciezka</c> do siebie.
        /// </summary>
        /// <param name="other">porownywana sciezka</param>
        /// <returns>true, jesli obie sciezki opisuja ten sam cykl</returns>
        public override bool Equals(object other)
        {
            if (other == null)
                return false;
            Sciezka inna = other as Sciezka;
            if (inna == null)
                return false;
            if (this.Dlugosc != inna.Dlugosc)
                return false;
            int j = inna.pozycjaMiasta(this[0]);
            for (int i = 1; i < Dlugosc; i++)
            {
                if (inna.pozycjaMiasta(this[i]) != ((++j) % Dlugosc))
                    return false;
            }

            return true;
        }

        /// <summary>
        /// Dostep do miasta na danej pozycji w sciezce.
        /// </summary>
        public int this[int pozycja]
        {
            get
            {
                if (pozycja < 0 || pozycja >= sciezka.Length)
                    return 0;
                else
                    return sciezka[pozycja];
            }
            set
            {
                if (pozycja >= 0 && pozycja < sciezka.Length)
                    sciezka[pozycja] = value;

            }
        }

        /// <summary>
        /// Operator krzyzowania (cross-over). Krzyzuje obiekt na ktorym wywolany z innym
        /// a nastepnie zwraca dwoch potomkow.
        /// </summary>
        /// <param name="s1">pierwszy rodzic</param>
        /// <param name="s2">drugi rodzic</param>
        /// <returns>tablica zawierajaca dwoch potomkow</returns>
        public static Sciezka[] PMX(Sciezka s1, Sciezka s2)
        {
            Sciezka[] wynik = new Sciezka[2];
            wynik[0] = s1.klonuj();
            wynik[1] = s2.klonuj();
            //zalozenie jest takie, ze ciecie moze przypasc przed lub po dowolnym miescie
            //ale ciecia nie moga sie pokrywac, zeby doszlo chocby do minimalnej wymiany

            int ciecie1 = generator.Next(s1.Dlugosc + 1), ciecie2;
            do
                ciecie2 = generator.Next(s1.Dlugosc + 1);
            while (ciecie1 == ciecie2);

            if (ciecie1 > ciecie2)
            {
                int temp = ciecie1;
                ciecie1 = ciecie2;
                ciecie2 = temp;
            }

            ArrayList uzyte0 = new ArrayList();
            ArrayList uzyte1 = new ArrayList();
            for (int i = ciecie1; i < ciecie2; i++)
            {
                wynik[0][i] = s2[i];
                wynik[1][i] = s1[i];
                uzyte1.Add(wynik[0][i]);
                uzyte0.Add(wynik[1][i]);
            }

            for (int i = 0; i < s1.Dlugosc; i++)
            {
                if (i >= ciecie1 && i < ciecie2)
                {
                    continue;
                }

                while (uzyte1.Contains(wynik[0][i]))
                {
                    wynik[0][i] = (int)uzyte0[uzyte1.IndexOf(wynik[0][i])];
                }

                while (uzyte0.Contains(wynik[1][i]))
                {
                    wynik[1][i] = (int)uzyte1[uzyte0.IndexOf(wynik[1][i])];
                }
            }

            return wynik;
        }

        public static Sciezka[] CKM(Sciezka s1, Sciezka s2, Koszty koszty)
        {
            Sciezka[] wynik = new Sciezka[2];
            wynik[0] = s1.klonuj();
            wynik[1] = s2.klonuj();
            //zalozenie jest takie, ze ciecie moze przypasc przed lub po dowolnym miescie
            //ale ciecia nie moga sie pokrywac, zeby doszlo chocby do minimalnej wymiany

            int dlugoscPodciagu;

            do
                dlugoscPodciagu = generator.Next(s1.Dlugosc);
            while (dlugoscPodciagu < 2);

            int najmniejszyKoszt = int.MaxValue;
            int najlepszeCiecie1 = 0;
            int najlepszeCiecie2 = 0;

            for (int i = 0; i < s1.Dlugosc; i++)
            {
                int ciecie1 = i;
                int ciecie2;

                if (ciecie1 + dlugoscPodciagu <= s1.Dlugosc)
                {
                    ciecie2 = ciecie1 + dlugoscPodciagu;
                }
                else
                {
                    int temp = ciecie1 + dlugoscPodciagu - s1.Dlugosc;
                    ciecie2 = ciecie1;
                    ciecie1 = temp;
                }

                int kosztPodciagu = s1.ObliczKosztPodciagu(koszty, ciecie1, ciecie2);

                if (najmniejszyKoszt > kosztPodciagu)
                {
                    najmniejszyKoszt = kosztPodciagu;
                    najlepszeCiecie1 = ciecie1;
                    najlepszeCiecie2 = ciecie2;
                }
            }




            ArrayList uzyte0 = new ArrayList();
            ArrayList uzyte1 = new ArrayList();
            for (int i = najlepszeCiecie1; i < najlepszeCiecie2; i++)
            {
                wynik[0][i] = s2[i];
                wynik[1][i] = s1[i];
                uzyte1.Add(wynik[0][i]);
                uzyte0.Add(wynik[1][i]);
            }

            for (int i = 0; i < s1.Dlugosc; i++)
            {
                if (i >= najlepszeCiecie1 && i < najlepszeCiecie2)
                {
                    continue;
                }

                while (uzyte1.Contains(wynik[0][i]))
                {
                    wynik[0][i] = (int)uzyte0[uzyte1.IndexOf(wynik[0][i])];
                }

                while (uzyte0.Contains(wynik[1][i]))
                {
                    wynik[1][i] = (int)uzyte1[uzyte0.IndexOf(wynik[1][i])];
                }
            }

            return wynik;
        }

        private int ObliczKosztPodciagu(Koszty koszty, int ciecie1, int ciecie2)
        {
            int wynik = 0;
            for (int i = ciecie1; i < ciecie2; i++)
            {
                wynik += koszty[sciezka[i], sciezka[(i + 1) % sciezka.Length]];
            }

            return wynik;
        }

		/// <summary>
		/// Ustawia miasta na losowych pozycjach.
		/// </summary>
		/// <returns>ten sam obiekt <c>Sciezka</c> ale z inna lista miast</returns>
		public Sciezka losuj()
		{
			int wartLos = 0;
			for (int i = 0; i < sciezka.Length; i++)
			{
				sciezka[i] = 0;
			}
			for (int i = 0; i < sciezka.Length; i++)
			{
				do
					wartLos = generator.Next(sciezka.Length);
				while (sciezka[wartLos] > 0);
				sciezka[wartLos] = i+1;
			}
			return this;
		}

		/// <summary>
		/// Glebokie klonowanie obiektu <c>Sciezka</c>.
		/// </summary>
		/// <returns>sklonowany obiekt</returns>
		public Sciezka klonuj()
		{
			Sciezka wynik = new Sciezka(this.sciezka.Length);
			for (int i = 0; i < sciezka.Length; i++)
				wynik.sciezka[i] = this.sciezka[i];

			return wynik;
		}

		/// <summary>
		/// Oblicza koszt sciezki na podstawie kosztow przekazanych przez parametr.
		/// Metoda oblicza sume kosztow wszystkich karwedzi 
		/// (takze pomiedzy ostatnim a pierwszym miastem).
		/// </summary>
		/// <param name="k">definicja kosztow</param>
		/// <returns>laczny koszt sciezki</returns>
		public int kosztSciezki(Koszty k)
		{
			if (k.IloscMiast != sciezka.Length)
				throw new ArgumentException("koszty zdefiniowane dla sciezek o innej ilosci miast", "k");
			int wynik = 0;
			for (int i = 0; i < sciezka.Length; i++)
			{				
				wynik += k[sciezka[i], sciezka[(i+1)%sciezka.Length]];
			}
			return wynik;
		}

		/// <summary>
		/// Cokolwiek udziwniona wersja operatora mutacji. Wybiera dwa sasiednie miasta na sciezce
		/// i po prostu je zamienia.
		/// </summary>
		public void mutuj()
		{
			int p1 = generator.Next(sciezka.Length);
			int p2 = (p1 + 1) % Dlugosc;
			/*while (p1 == p2)
				p2 = generator.Next(sciezka.Length);*/

			int temp = sciezka[p1];
			sciezka[p1] = sciezka[p2];
			sciezka[p2] = temp;
		}
	
		/// <summary>
		/// Metoda zwraca pozycje miasta. Miasto musi byc w zakresie. Pozycje zaczynaja sie od zera.
		/// </summary>
		/// <param name="miasto">miasto dla ktorego szukamy pozycji</param>
		/// <returns>pozycje miasta lub -1</returns>
		public int pozycjaMiasta(int miasto)
		{
			if (miasto > 0 && miasto <= sciezka.Length)
			{
				for(int i = 0; i < sciezka.Length; i++)
				{
					if (sciezka[i] == miasto)
						return i;
				}
			}
			return -1;
		}

		/// <summary>
		/// Sprawdza poprawnosc sciezki.
		/// </summary>
		/// <returns><c>true</c> jesli poprawna</returns>
		public bool isValid()
		{			
			for (int i = 0; i < sciezka.Length; i++)
			{
				if (pozycjaMiasta(i+1) == -1)
					return false;
			}
			return true;
		}

		/// <summary>
		/// Ustawia wszystkie pozycje na sciezce na zero.
		/// </summary>
		private void zerujSciezke()
		{
			for (int i = 0; i < sciezka.Length; i++)
				sciezka[i] = 0;
		}	
	}
}
